package com.techyuan.algorithm.structure.tree;

import com.techyuan.algorithm.utils.PrintUtil;
import com.techyuan.algorithm.utils.SortUtils;

/**
 * 二叉搜索树
 * Created by tianjuntao on 2016/12/12.
 */
public class BSTree {
    protected TreeNode root;

    public BSTree() {
        root = TreeNode.nil;
    }

    public BSTree(TreeNode root) {
        this.root = root;
    }

    public TreeNode search(Integer k) {
        return rSearch(root, k);
    }

    public TreeNode getRoot() {
        return root;
    }

    /**
     * 递归查找
     *
     * @param x
     * @param k
     * @return
     */
    private static TreeNode rSearch(TreeNode x, Integer k) {
        if (x.isNil() || x.getKey() == k)
            return x;
        if (k < x.getKey())
            return rSearch(x.getLeft(), k);

        return rSearch(x.getRight(), k);
    }

    private static TreeNode search(TreeNode x, Integer k) {
        while (!x.isNil() && x.getKey() != k) {
            if (k < x.getKey())
                x = x.getLeft();
            else
                x = x.getRight();
        }

        return x;
    }

    /**
     * 查找最小节点
     *
     * @return
     */
    public TreeNode minimux(TreeNode x) {
        while (!x.getLeft().isNil()) {
            x = x.getLeft();
        }
        return x;
    }

    /**
     * 查找最大节点
     *
     * @return
     */
    public TreeNode maximux(TreeNode x) {
        while (!x.getRight().isNil()) {
            x = x.getRight();
        }
        return x;
    }

    /**
     * 查找节点的后继
     *
     * @param x
     * @return
     */
    public TreeNode successor(TreeNode x) {
        if (!x.getRight().isNil())
            return minimux(x.getRight());
        TreeNode y = x.getParent();
        while (!y.isNil() && x == y.getRight()) {
            x = y;
            y = y.getParent();
        }
        return y;
    }

    public void insert(BSTree tree, Integer z) {
        insert(tree, new TreeNode(root.getNil(), root.getNil(), root.getNil(), z));
    }

    protected void insert(BSTree tree, TreeNode z) {
        TreeNode y = root.getNil();
        TreeNode x = tree.root;
        while (!x.isNil()) {
            y = x;
            if (z.getKey() < x.getKey())
                x = x.getLeft();
            else
                x = x.getRight();
        }
        z.setParent(y);
        if (y.isNil())
            tree.root = z;
        else if (z.getKey() < y.getKey())
            y.setLeft(z);
        else
            y.setRight(z);
    }

    public TreeNode deleteNode(BSTree tree, Integer z) {
        TreeNode node = search(tree.root, z);
        if (!node.isNil()) {
            deleteNode(tree, node);
        }
        return node;
    }

    protected TreeNode deleteNode(BSTree tree, TreeNode z) {
        if (z.getLeft().isNil())
            transplant(tree, z, z.getRight());
        else if (z.getRight().isNil())
            transplant(tree, z, z.getLeft());
        else {
            TreeNode minNode = successor(z);
            if (minNode.getParent() != z) {
                transplant(tree, minNode, minNode.getRight());
                minNode.setRight(z.getRight());
                minNode.getRight().setParent(minNode);
            }
            transplant(tree, z, minNode);
            minNode.setLeft(z.getLeft());
            minNode.getLeft().setParent(minNode);
        }
        return z;
    }

    public void transplant(BSTree tree, TreeNode u, TreeNode v) {
        if (u.getParent().isNil())
            tree.root = v;
        else if (u == u.getParent().getLeft()) {
            u.getParent().setLeft(v);
        } else {
            u.getParent().setRight(v);
        }
        if (!v.isNil()) {
            v.setParent(u.getParent());
        }
    }

    public static void main(String[] args) {
        int[] arr = SortUtils.createRandomList(5, 100);
        PrintUtil.printArrPretty(arr);
        BSTree tree = new BSTree();
        for (int v : arr)
            tree.insert(tree, new TreeNode(TreeNode.nil, TreeNode.nil, TreeNode.nil, v));
        TreeUtils.preorderTreeWalk(tree.root);//先序
        tree.deleteNode(tree, arr[2]);
        System.out.println();
        TreeUtils.preorderTreeWalk(tree.root);//先序
    }
}
